/**
 * @program: LeetCode
 * @description: LeetCode : 134. 加油站
 * @author: WXY
 * @create: 2023-01-20 19:17
 * @Version 1.0
 **/
public class Num134_canCompleteCircuit {
    public static int canCompleteCircuit1(int[] gas, int[] cost) {
        for (int i = 0; i < gas.length; i++) {
            int rest = gas[i] - cost[i];
            int index = (i + 1) % gas.length;
            while (rest >= 0 && index != i) {
                rest += gas[index] - cost[index];
                index = (index + 1) % gas.length;
            }
            if (rest >= 0 && index == i) {
                return i;
            }
        }
        return -1;
    }

    //前提已经确定可以跑完全程，totalSum >= 0有两种情况，
    //1. curSum 就没有小于0，全部是大于0,说明从0开始就可以跑完全程
    //2. curSum 在中途index的位置小于0 ，假设在[0...index] curSum < 0,那么在[index + 1...length]上curSum大于0，
    //那么从index + 1 开始一定可以跑完全程
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = 0;
        for (int i = 0; i < gas.length; i++) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (curSum < 0) {
                start = i + 1;
                curSum = 0;
            }
        }
        if (totalSum < 0)return -1;
        return start;
    }
}
